package com.sheng.leetcode.year2022.month08.day28;

import org.junit.Test;

import java.math.BigDecimal;

/**
 * @author liusheng
 * @date 2022/08/29
 *
 * 793. 阶乘函数后 K 个零
 *
 *  f(x) 是 x! 末尾是 0 的数量。回想一下 x! = 1 * 2 * 3 * ... * x，且 0! = 1 。
 * 例如， f(3) = 0 ，因为 3! = 6 的末尾没有 0 ；而 f(11) = 2 ，因为 11!= 39916800 末端有 2 个 0 。
 * 给定 k，找出返回能满足 f(x) = k 的非负整数 x 的数量。
 *
 * 示例 1：
 * 输入：k = 0
 * 输出：5
 * 解释：0!, 1!, 2!, 3!, 和 4! 均符合 k = 0 的条件。
 *
 * 示例 2：
 * 输入：k = 5
 * 输出：0
 * 解释：没有匹配到这样的 x!，符合 k = 5 的条件。
 *
 * 示例 3:
 * 输入: k = 3
 * 输出: 5
 *
 * 提示:
 *
 * 0 <= k <= 10^9
 */
public class LeetCode0793 {

    @Test
    public void test01() {
//        int k = 0;
//        int k = 5;
        int k = 3;
        System.out.println(new Solution().preimageSizeFZF(k));
    }
}
//class Solution {
//    public int preimageSizeFZF(int k) {
//        // 符合条件的阶乘的个数（超时）
//        int count = 0;
//        // 阶乘值
//        BigDecimal big = new BigDecimal(1);
//        // 0的数量
//        int num = 0;
//        // 阶乘过程中2的数量和5的数量累计
//        int bn2 = 0, bn5 = 0;
//        for (int i = 0; i < Integer.MAX_VALUE; i++) {
//            // 计算阶乘后的0的数量
//            BigDecimal bigDecimal = new BigDecimal(i);
//            if (i != 0) {
//                big = big.multiply(bigDecimal);
//                // 乘积大于10时，才会出现0
//                if (big.compareTo(BigDecimal.TEN) >= 0) {
//                    // 0的个数等于阶乘里面10的个数，10可以分为2和5
//                    // 计算本次乘以的数i中包含的2的个数，并将其加到bn2的累计中
//                    while (bigDecimal.divideAndRemainder(new BigDecimal(2))[1].compareTo(BigDecimal.ZERO) == 0) {
//                        bn2++;
//                        bigDecimal = bigDecimal.divideAndRemainder(new BigDecimal(2))[0];
//                    }
//                    // 计算本次乘以的数i中包含的5的个数，并将其加到bn5的累计中
//                    while (bigDecimal.divideAndRemainder(new BigDecimal(5))[1].compareTo(BigDecimal.ZERO) == 0) {
//                        bn5++;
//                        bigDecimal = bigDecimal.divideAndRemainder(new BigDecimal(5))[0];
//                    }
//                    // 取得2和5的累计中较小的一个，即为0的个数
//                    num = Math.min(bn2, bn5);
//                }
//                // 符合条件
//                if (num == k) {
//                    count++;
//                // 当0的个数超过k时，跳出循环
//                } else if (num > k) {
//                    break;
//                }
//            // 如果i == 0并且k == 0时
//            } else if (k == 0) {
//                count++;
//            }
//        }
//        return count;
//    }
//}

//class Solution {
//    public int preimageSizeFZF(int k) {
//        return (int) (help(k + 1) - help(k));
//    }
//
//    public long help(int k) {
//        long r = 5L * k;
//        long l = 0;
//        while (l <= r) {
//            long mid = (l + r) / 2;
//            if (zeta(mid) < k) {
//                l = mid + 1;
//            } else {
//                r = mid - 1;
//            }
//        }
//        return r + 1;
//    }
//
//    public long zeta(long x) {
//        long res = 0;
//        while (x != 0) {
//            res += x / 5;
//            x /= 5;
//        }
//        return res;
//    }
//}

//数学 + 二分
//对于一个 n! = 1 x 2 x ... x (n - 1) x n 而言，
//其最终结果尾部包含 0 的数量取决于其被累乘 10 的次数，而 10 可通过质因数 2 和 5 相乘而来，因此假设对 n! 进行阶乘分解，最终分解出 2^p 和 5^q
//的话，那么最终结果尾部包含 0 的个数为 q 个（可证明 p >= q 始终满足）。
//因此原问题转化为：在非负整数中，有多少个数进行阶乘分解后，所含质因数 5 的个数恰好为 k 个。
//同时我们可知：随着 n 的增大，其所能分解出来的 5 的个数必然是递增的。
//基于此，我们可以通过「二分 + 容斥原理」来得出分解 5 个数恰好为 k 的连续段长度。
//假设我们存在函数 f(k) 可得到非负整数中分解 5 个数为小于等于 k 的个数，那么最终 f(k) - f(k - 1) 即是答案。
//在单调函数上求解小于等于 k 分割点，可通过「二分」来做。剩下的问题是，如何求得给定 x 时，其阶乘分解所包含 5 个个数，这可以通过 O(logx) 的筛法来做。
//最后还要确定二分的值域，由于我们是求阶乘分解中 5 的个数，因此值域的上界为 5k，利用 k 的范围为 1e9，直接取成 1e10 即可。
//
//代码：
//
class Solution {
    public int preimageSizeFZF(int k) {
        if (k <= 1) {
            return 5;
        }
        return f(k) - f(k - 1);
    }
    int f(int x) {
        long l = 0, r = (long) 1e10;
        while (l < r) {
            long mid = l + r + 1 >> 1;
            if (getCnt(mid) <= x) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return (int) r;
    }
    long getCnt(long x) {
        long ans = 0;
        while (x != 0) {
            ans += x / 5;
            x /= 5;
        }
        return ans;
    }
}
//
//作者：AC_OIer
//链接：https://leetcode.cn/problems/preimage-size-of-factorial-zeroes-function/solution/by-ac_oier-pk9g/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

//class Solution {
//
//     // 按照数据规律求解阶乘
//     // 1个5      5   1
//     // 2个5 =    25  6   实际相当于 5个1个5，然后再加25自身是两个5，所以得到的是 5+1 = 6
//     // 3个5 =    125 31  相当于5个25，然后加自身125又多了一个5 所以的（5+1）*5+1=31
//     // 按照这个规律，则后续公式可以f(2)=f(1)*5+1 f(1)=1 则 f(x+1) = f(x)*5+1  x是5的次幂数
//
//   public int preimageSizeFZF(int K) {
//  int last=1;
//    while(last<K)
//        last=5*last+1;
//    while(last>1){
//        if(last-1==K)
//            return 0;
//        last=(last-1)/5;
//        K%=last;
//    }
//    return 5;
//    }
//}
